﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace ProjectEulerIssues
{
	public partial class Program
	{
		[SolutionInfo(Links = "http://www.mathblog.dk/project-euler-103-special-subset-sum/")]
		private static dynamic Problem103()
		{
			const int LOWER_BOUND = -3;
			const int UPPER_BOUND = 3;

			Func<List<int>, bool> checkRuleOne = (List<int> v) => 
			{
				var vSizes = new HashSet<int>();
				var vOld = new List<HashSet<int>>();
				for (int i = 0; i < v.Count; i++)
				{
					vOld.Add(new HashSet<int>() { i });
					if (vSizes.Contains(v[i]))
					{
						return false;
					}
					vSizes.Add(v[i]);
				}
				var vNew = new List<HashSet<int>>();
				
				for (int i = 2; i <= v.Count; i++)
				{
					foreach (var vOldi in vOld)
					{
						var vOldiMax = vOldi.Max();
						for (int j = vOldiMax + 1; j < v.Count; j++)
						{
							var vNewi = new HashSet<int>(vOldi);
							vNewi.Add(j);
							vNew.Add(vNewi);
							var size = vNewi.Select(vni => v[vni]).Sum();
							if (vSizes.Contains(size))
							{
								return false;
							}
							vSizes.Add(size);
						}
					}
					vOld = vNew;
					vNew = new List<HashSet<int>>(); 
				}
				return true;
			};

			Func<List<int>, bool> checkRuleTwo = (List<int> v) => 
			{
				int sum1 = v[0];
				int sum2 = 0;

				for (int i = 0; i < v.Count / 2; i++)
				{
					sum1 += v[i + 1];
					sum2 += v[v.Count - i - 1];

					if (sum1 <= sum2)
						return false;
				}
				return true;
			};

			int minSum = 0;
			string min = null;

			Action<List<int>, int, int> processNext = null;
			processNext = (List<int> v, int pos, int maxSum) => 
			{
				if (pos == v.Count)
				{
					var sum = v.Sum();
					if (sum > maxSum || !(minSum == 0 || sum < minSum))
					{
						return;
					}
					var vSort = v.ToList();
					vSort.Sort();
					if (!checkRuleTwo(vSort))
					{
						return;
					}
					if (!checkRuleOne(vSort))
					{
						return;
					}
					minSum = sum;
					min = string.Empty;
					vSort.ForEach(vs => min += vs.ToString());
				}
				else
				{
					for (int i = LOWER_BOUND; i <= UPPER_BOUND; i++)
					{
						v[pos] += i;
						processNext(v, pos + 1, maxSum);
						v[pos] -= i;
					}
				}
			};

			Func<string> solve = () => 
			{
				var v = new List<int>() { 11, 18, 19, 20, 22, 25 };
				var avV = (v.Sum() / v.Count) + 1;
				for (var i = 0; i < v.Count; i++)
				{
					v[i] += avV;
				}
				v.Insert(0, avV);
				var maxSum = v.Sum();
				processNext(v, 0, maxSum);
				return min;
			};
			return solve();
		}
	}
}
